# 两数相除： https://leetcode-cn.com/problems/divide-two-integers/submissions/


# 减法代替除法
class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        """ 使用减法, 累计计算，缺点是 当位被除数，除数相差过大时，会导致超时 """
        # 考虑越界问题: 负数 除以 -1 得到整数，溢出，边界值
        if dividend == -1 * 2**31 and divisor == -1:
            return 2**31 - 1

        # 计算最终符号: 异或运算，当都为 1 或者都为 -1 时， 返回 1， 否则 是负数， 返回 0
        sign = -1 if (dividend > 0) ^ (divisor > 0) else 1
        a, b = abs(dividend), abs(divisor)
        rst = 0
        while a - b >= 0:
            rst += 1
            a -= b
        
        return sign * rst 


# 减法代替除法优化， 每次减去 除数的倍数，递归实现。 时间复杂度O(log n^2)
class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        """ 减法优化， 每次尝试减去 除数的 倍数， 是个递归过程 """
        # 考虑越界问题: 负数 除以 -1 得到整数，溢出，边界值
        if dividend == -1 * 2**31 and divisor == -1:
            return 2**31 - 1
        # 计算最终符号: 异或运算，当都为 1 或者都为 -1 时， 返回 1， 否则 是负数， 返回 0
        sign = -1 if (dividend > 0) ^ (divisor > 0) else 1
        a, b = abs(dividend), abs(divisor)
        
        def getTruncate(a, b):
            if a < b: return 0

            # n： 记录右移次数
            n = 0
            B = b
            while a > (B << 1):
                n += 1
                B = B << 1
            
            return 2 ** n + getTruncate(a - B, b) 
        
        rst = getTruncate(a, b)
        return sign * rst


# 上面的 bug， n 使用到了 乘法， 这里也变成 位运算。 另外有两个要注意的地方
def getTruncate(a, b):
            if a < b: return 0

            # n： 记录为 除数（b）的倍数
            n = 1
            B = b
            # bug1. B << 2 可能大于 32位整形的最大范围，其他语言需要定义为 long型
            # bug2. B 为 -2 ** 31 时，在其他静态语言中（java）， 左移得到的值还是 -2**31，会陷入无限死循环。  
            # Python大整数不用考虑上面的俩问题， 代码正常跑过
            while a > (B << 1):
                n = n << 1
                B = B << 1
            
            return n + getTruncate(a - B, b) 


# 环境限制 只要32 位整数类型， 所有不能使用 long型， 代码还需要优化， 我没有往下看下去了
# 实际上感觉再进行 位运算前，先判断当前值，是否大于 2**31 - 1 的一半就行，没去代码尝试了
